// GCD = Greatest Common Divisor

/* Note:
 gcd_b, gcd_s, gcd_q, gcd_r
 are the same length
 according to the math theory of GCD calcualtion
 */
cintFIFO gcd_b = new cintFIFO(); // big number
cintFIFO gcd_s = new cintFIFO(); // small number
cintFIFO gcd_q = new cintFIFO(); // quotient
cintFIFO gcd_r = new cintFIFO(); // remainder

int gcd_final; // final GCD result

void gcd(int m, int n) {
  println("\n\nabout to calculate Greatest Common Divisor of " + m + " & " + n);

  gcd_b.clear();
  gcd_s.clear();
  gcd_q.clear();
  gcd_r.clear();

  int b, s; // big small
  if (m > n) {
    b = m;
    s = n;
  } else {
    b = n;
    s = m;
  }
  gcd_recursion(b, s);
}

void gcd_recursion(int b, int s) {

  gcd_b.in(b);
  gcd_s.in(s);

  int q; // quotient
  int r; // remainder
  // big / small = quotient --- remainder
  q = b / s;
  r = b % s;
  gcd_q.in(q);
  gcd_r.in(r);

  println(b + " / " + s + " = " + q + " --- " + r);

  if (r == 0) {
    gcd_final = s;
    println("GCD = " + gcd_final);
    return;
  } else {
    gcd_recursion(s, r); // recursion (s is bigger than r always)
  }
}
